//https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
package codeRandomThoughts.Test28找出字符串中第一个匹配项的下标;

public class Solution {
    //其实就是KMP 模式匹配
    //KMP是研究这个算法的三个人的名字
    //重要的一环是理解next数组
    //next数组是找最大的相同前缀后缀
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0)
            return 0;

        //根据needle得到next数组
        int[] next = getNextFromPattern(needle);
        int i = 0;
        int j = -1;

        //遍历文本串
        for (i=0;i<haystack.length();i++){
            //不相同,回退
            while(j>=0 && haystack.charAt(i)!=needle.charAt(j+1)){
                j=next[j];
            }
            if ( haystack.charAt(i)==needle.charAt(j+1)){
                j++;
            }

            //判断是否匹配到末尾
            if (j==(needle.length()-1)){
                return (i-needle.length()+1);
            }
        }

        return -1;
    }

    int[] getNextFromPattern(String string) {
        char[] pattern = string.toCharArray();
        //首先创建next数组
        int[] next = new int[pattern.length];

        //j是前缀的末尾,i是后缀的末尾
        int i = 1;
        int j = -1;//指向数组开头的前面
        //next第一项肯定为j
        next[0] = j;

        for (i = 1; i < pattern.length; i++) {
            //如果j指向的字符与i指向的字符不等,即前后缀末尾字符不相等,需要回退
            //如果j回退到-1,就退出循环
            while (j >= 0 && pattern[i] != pattern[j + 1]) {
                j = next[j];//向前回退
            }

            //最长相等前后缀能够延长
            if (pattern[i] == pattern[j + 1]) {
                j++;
            }
            next[i] = j;
        }

        return next;
    }

    //调用String的库函数
    public int strStr2(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
}
